package com.xpchenfrank.test.supplier;

/**
 * @author xpchen
 * @time 2019\2\21 0021 3:26
 * @Description
 * @copyright Wuxi Yazuo ,Ltd.copyright 2015-2025
 */
public class LinkedListPractice20190221 {

    public static void main(String[] args) {
        ListNode headNode = null;
        ListNode listNode = new ListNode(1);
        headNode = listNode;
        listNode.next = new ListNode(2);
        listNode = listNode.next;
        listNode.next = new ListNode(3);
        listNode = listNode.next;
        listNode.next = new ListNode(4);
        listNode = listNode.next;
        listNode.next = new ListNode(5);
        listNode = listNode.next;

        ListNode listNodeResult = LinkedListPractice20190221.lastNNodeNormal(headNode, 5);

        System.out.println("result is " + listNodeResult.val);

        listNodeResult = LinkedListPractice20190221.lastNNodeNormal(headNode, 1);

        System.out.println("result is " + listNodeResult.val);

        listNodeResult = LinkedListPractice20190221.lastNNodeNormal(headNode, 2);

        System.out.println("result is " + listNodeResult.val);

        //listNodeResult = LinkedListPractice20190221.lastNNodeNormal(headNode, 6);

        //System.out.println("result is " + listNodeResult.val);

        /************************* 另一种解题方法 ******************************************/
        listNodeResult = LinkedListPractice20190221.lastNNodeAdvanced(headNode, 5);

        System.out.println("----result is " + listNodeResult.val);

        listNodeResult = LinkedListPractice20190221.lastNNodeAdvanced(headNode, 1);

        System.out.println("result is " + listNodeResult.val);

        listNodeResult = LinkedListPractice20190221.lastNNodeAdvanced(headNode, 2);

        System.out.println("result is " + listNodeResult.val);

        listNodeResult = LinkedListPractice20190221.lastNNodeAdvanced(headNode, 6);

        System.out.println("result is " + listNodeResult.val);

//        while(listNodeResult != null) {
//            System.out.println(listNodeResult.val);
//            listNodeResult = listNodeResult.next;
//        }
    }

    public static ListNode reserveNode(ListNode head) {

        ListNode preNode = null;
        ListNode curr = head;

        while(curr != null) {
            ListNode nextNode = curr.next;
            head = curr;
            curr.next = preNode;
            preNode = curr;
            curr = nextNode;

        }

        return head;

    }

    /**
     * 普通解法
     *
     * @param head
     * @param lastN
     * @return
     */
    public static ListNode lastNNodeNormal(ListNode head, int lastN) {

        int size = 0;

        ListNode tempNode = head;
        while(tempNode != null) {
            tempNode = tempNode.next;
            size++;
        }

        int index = size - lastN;
        if(index > 0) {
            int indexCount = 0;
            tempNode = head;
            while(tempNode != null) {
                tempNode = tempNode.next;
                indexCount++;

                if(indexCount == index) {
                    break;
                }
            }
            return tempNode;
        } else if (index < 0) {
            throw new IllegalArgumentException("lastN is greater than size");
        } else {
            return head;
        }

    }

    /**
     * 双指针解法
     *
     * @param head
     * @param lastN
     * @return
     */
    public static ListNode lastNNodeAdvanced(ListNode head, int lastN) {

        ListNode slowCur = head;
        ListNode fastCur = head;

        int tempLastN = lastN;
        while(tempLastN > 0 && fastCur != null) {
            fastCur = fastCur.next;
            tempLastN--;
        }

        if(tempLastN > 0) {
            throw new IllegalArgumentException("lastN is greater than size");
        }

        while(fastCur != null) {
            fastCur = fastCur.next;
            slowCur = slowCur.next;
        }

        return slowCur;


    }



}
